public class Solution {
    public static void main(String[] args) {
        /**
         * 归并排序*/
        Solution s = new Solution();
        int[] nums = new int[]{1,1,2,2,7,7,5,5,1,1};
        mergeSort(0, nums.length-1, nums);
        for(int e: nums) {
            System.out.print(e + " ");
        }
    }

    public int[] sortArray(int[] nums) {
        mergeSort(0, nums.length-1, nums);
        return nums;
    }

    public static void mergeSort(int left, int right, int[] nums) {
        /**
         * 归并排序-递归实现*/
        // 1 递归出口
        if(left == right) {
            return;
        }

        // 2 找分割点（偏左）
        int mid = left + (right - left) / 2;

        // 3 递归下去分割数组
        mergeSort(left, mid, nums);
        mergeSort(mid+1, right, nums);

        // 4 合并（返回的子分支是有序的，我们仅需将两个子分支合并，思想与合并有序链表相似）
        merge(left, mid, mid+1, right, nums);

    }

    public static void merge(int l1, int r1, int l2, int r2, int[] nums) {
        /**
         * 合并两个有序数组并实际写入至原数组中*/
        // 1 预处理
        int baseIndex = l1;
        int[] tempArray = new int[r2-l1+1];

        // 2 合并排序临时写入
        int i = 0;
        while(l1 <= r1 && l2 <= r2) {
            if(nums[l1] <= nums[l2]) {
                tempArray[i++] = nums[l1++];
            } else {
                tempArray[i++] = nums[l2++];
            }
        }
        while(l1 <= r1) {
            tempArray[i++] = nums[l1++];
        }
        while(l2 <= r2) {
            tempArray[i++] = nums[l2++];
        }

        // 3 写入原数组
        for(int k = 0; k < tempArray.length; k++) {
            nums[baseIndex + k] = tempArray[k];
        }
    }

    public static void swap(int a, int b, int[] nums) {
        /**
         * 交换a、b下标元素*/
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}
